package com.LeeCode;

import java.util.TreeMap;

/**
 * 我的日程安排表 III
 */

public class Code732 {
    public static void main(String[] args) {
        MyCalendarThree myCalendarThree = new Code732().new MyCalendarThree();
        System.out.println(myCalendarThree.book(10, 20));
        System.out.println(myCalendarThree.book(50, 60));
        System.out.println(myCalendarThree.book(10, 40));
        System.out.println(myCalendarThree.book(5, 15));
        System.out.println(myCalendarThree.book(5, 10));
        System.out.println(myCalendarThree.book(25, 55));
    }

    class MyCalendarThree {
        private TreeMap<Integer, Integer> diff;

        public MyCalendarThree() {
            diff = new TreeMap<>();
        }

        public int book(int startTime, int endTime) {
            // 更新差分：[startTime, endTime) 区间 +1
            diff.put(startTime, diff.getOrDefault(startTime, 0) + 1);
            diff.put(endTime, diff.getOrDefault(endTime, 0) - 1);

            // 遍历所有关键点，计算前缀和，求最大值
            int maxBooking = 0;
            int current = 0;

            for (int delta : diff.values()) {
                current += delta;
                maxBooking = Math.max(maxBooking, current);
            }

            return maxBooking;
        }
    }
}
